/*!
\file AlgAStar.h
\brief Contains definition of A* Algorithm.
\ingroup Plugins
*/

#ifndef ALGASTAR_H
#define ALGASTAR_H

#include<QApplication>
#include<Graph.h>
#include<Algorithm.h>
#include<Visualizer.h>
#include<ContainerElement.h>
#include<QList>
#include<math.h>
/*!
\defgroup Plugins Plugins Group
This group contains all plugins. This is not a module, as its members do not depend on or know of each other. This group depends on \ref Algorithm.
@{
*/

/*!
\struct str_data
\brief Contains f, g, h, parentID data which is used by A*.
\typedef Data
\brief Typedef for str_data.
*/
typedef struct str_data{
	str_data( double g = 0.0, double h = 0.0, double f = 0.0, int parentID = -1 ){
		this->f = f;
		this->g = g;
		this->h = h;
		this->parentID = parentID;
	}//!< Constructor.
	double f; //!< Estimated distance from start to dest over this.
	double g; //!< Distance travelled from start to this.
	double h; //!< Estimated distance from this to dest.
	int parentID; //!< ID of parent for backtracking.
}Data;

/*!
\struct str_coordinates
\brief Simple struct to represent (x, y) coordinates.
\typedef Coordinates
\brief Typedef for str_coordinates.
*/

typedef struct str_coordinates{
	str_coordinates(double x, double y){
		this->x = x;
		this->y = y;
	}//!< Constructor if x and y are known already.
	str_coordinates( const char *data ){
		sscanf( data, "\"%lf, %lf\"", &x, &y );
	}//!< Constructor if x and y in string.
	double x; //!< x coordinate.
	double y; //!< y coordinate.
}Coordinates;

/*!
\class AlgAStar
\brief Implements A* algorithm.
*/

class AlgAStar: public Algorithm{
public:
	AlgAStar( Graph *g );
	//!< Constructor.
	~AlgAStar();
	//!< Destructor.
	void run();
	//!< Reimplementation of run function.
	void astar( const Node &start, const Node &dest );
	//!< Execute A* Algorithm from start to dest. Those are selected in run.
private:
	Container &closed(){ return container(1); }
	QList<Data*> m_closedData;
	
	Container &open(){ return container(0); }
	QList<Data*> m_openData;
	
	const Node *m_dest;
	
	void addToOpenList(const Node &node, int parentID = -1, double g = 0.0);
	void selectFromOpenList();
	double guessDistance( const Node &node );
	inline bool isInClosedList( const Node &n );
	void printRoute( const Node &n, Data *d );
	
	static Node otherNode( const Edge &e, const Node &n );
};

#endif 

/*! @} */ 
